1. Technical field
The invention relates to an image processing apparatus and method for rotating an original image formed of picture elements arranged in rows and columns, and more particularly, to an apparatus and method wherein combined horizontal shear and vertical shear operations are performed to generate addresses in an output image memory into which the first pels of each pel row are stored, and following which the addresses for all the other pels of each pel row in the memory are generated by a line generator.
2. Prior art and problems
In the prior art Affine transformation has been used to rotate an original image including picture elements arranged in rows aligned with an X axis and columns aligned with a Y axis.
The Affine transformation in a two-dimensional plane is represented as follows: EQU x'=ax+by+tx (1) EQU y'=cx+dy+ty (2)
where x and y are the coordinates before translation. The Affine transformation may be broken down into a linear transformation and a translation, as follows: ##EQU1##
The translation represents a shift amount in the X and Y directions and could be eliminated in the image rotation. The Affine transformation for the image rotation is expressed as follows: ##EQU2##
A picture element (pel) at a coordinate address (x, y) is moved to a coordinate address (x', y'). The linear transformation is decomposable into two shears and two scale transformation matrices as illustrated in equations (5.1)-(5.6), as follows: ##EQU3## where D=(ad-bc)
Two approaches using the equation (5.3) to perform the Affine transformation have been used to rotate the original image.
The first prior art approach is illustrated in FIG. 4. An original image 41 is stored in an image memory. In the first step, the original image is scaled in both the X and Y direction. That is, the number of pels in the image in the X direction is reduced and the number of pels in the Y direction is increased, but the total number of pels of the original image 41 is equal to the total number of pels in the ultimate rotated image 44. The term "scale" thus means that while the dimensions of the image may change there is no increase or reduction in the number of pels making up the image. The scaled image 42 is temporarily stored in a first intermediate memory space. The third and fourth matrices in the equation (5.3) correspond to the scaling operations. In the second step, all pels of the scaled image 42 are sequentially read out, and the scaled image 42 is horizontally sheared. The second matrix in the equation (5.3) corresponds to the horizontal shear operation. In the horizontal shear operation, the vertical columns of the scaled image 42 are inclined with respect to their original alignment with the Y axis, while the horizontal rows are maintained in alignment with the X direction. In other words, the addresses of the pels of the scaled image 42 are horizontally shifted. The horizontally sheared image 43 is temporarily stored in a second intermediate memory space. In the third step, all pels of the horizontally sheared image 43 are sequentially read out, and the image 43 is vertically sheared. The first matrix in equation (5.3 ) corresponds to the vertical shear operation. In the vertical shear operation, the horizontal rows of the image 43 are inclined with respect to the X axis. In other words, the addresses of all the pels of the image 43 are vertically shifted. The resulting rotated image 44 is stored in an output memory. The horizontal shift and vertical shift operations are known in the art as "transvection", but are called the horizontal shear and the vertical shear in this specification. It will be seen that the above-described rotating operations require two store operations into first and second intermediate memory spaces, and the calculation of the addresses of all the pels of the image to perform both the horizontal and vertical shear operations, all of which requires a relatively long time period. Consequently, an operator must wait a long time, after the rotation commands have been entered into the image processor, for a result.
IBM Technical Disclosure Bulletin, Vol. 13, No. 11, April 1971, pp. 3267-3268, discloses the use of the Affine transformation for rotating a two dimensional binary image. However, this article describes a different operational sequence from the above-described rotating operations but does also require intermediate memory spaces.
A second prior art approach is described in IBM Technical Disclosure Bulletin, Vol. 28, No. 10, March 1986, pp. 4330-4331. This article discloses the use of the equation (5.3), and the approach scales the original image in the X and Y directions in accordance with the third and fourth matrices, as well as performing the horizontal and vertical shear operations of the second and first matrices of equation (5.3). In the article, however, the addresses of all the pels of the scaled image are calculated in accordance with the second and first matrices to generate the horizontally and vertically sheared addresses, which are the addresses stored in an output memory. Consequently, the rotated version of the original image is directly stored in the output memory without requiring the intermediate memory spaces as in the first approach. Although the approach of this article reduces the processing time in comparison with the first approach, the technique of the article still requires a time period for calculating the addresses of all the pels of the scaled image.
It is clearly desirable and accordingly the object of the present invention to provide an image processing apparatus and method for rotating a two-dimensional original image at a much higher speed than possible with techniques of the prior art.